package leetcode_1201_1300;

import java.util.*;

public class LeeCode_1293 {
    public static void main(String[] args) {
        System.out.println(shortestPath(new int[][]{{0,1,0,0,0,1,0,0}, {0,1,0,1,0,1,0,1},
                {0,0,0,1,0,0,1,0}}, 1));
//        System.out.println(shortestPath(new int[][]{{0, 0, 0}, {1, 1, 0}, {0, 0, 0}, {0, 1, 1}, {0, 0, 0}}, 1));
    }
    private static int shortestPath(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        int[][] vis = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(vis[i], -1);
        }
        Deque<int[]> deque = new ArrayDeque<>();
        int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        deque.add(new int[]{0,0,0});
        vis[0][0] = 0;
        int step = 0;
        while (!deque.isEmpty()){
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                int[] p = deque.poll();
                int x = p[0], y = p[1];
                if (x == m - 1 && y == n - 1){
                    return step;
                }
                for (int[] dir : dirs) {
                    int nx = x + dir[0], ny = y + dir[1];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n || vis[nx][ny] != -1 &&
                            vis[nx][ny] <= p[2] + grid[nx][ny]  || p[2] + grid[nx][ny] > k){
                        continue;
                    }
                    vis[nx][ny] = p[2] + grid[nx][ny];
                    deque.offer(new int[]{nx, ny, p[2] + grid[nx][ny]});
                }
            }
            step++;
        }
        return -1;
    }
}